1. Field of the Invention
This invention is related to image processing techniques. More specifically, this invention is a system, method, and computer-readable medium for removing stereo matching errors caused by image occlusions.
2. Related Art
A stereo matching algorithm, which can produce a dense and sharp depth map as an active range finder, is a key technology for many stereo applications including object recognition, three-dimensional object modeling, vehicle navigation, and geometric inspection. In order to generate a three-dimensional map or image of a scene, however, different images of the scene must be matched properly. One of the major problems to properly matching points in the images is caused when occluding contours coincide. Occluding contours coincide when a point, which is visible in the right image, is not visible in the left image and therefore does not really have a matching point. Alternatively, occluding errors can also occur at the borders or edges of an object that are captured by a camera facing the object at different angles (called “occluding boundaries”). This is caused by the traditional correspondence procedure which will be described in further detail below.
The most standard situation where occluding contours occur is when other objects in the scene block the point of interest. When this occurs, area-based matching algorithms often give wrong disparity estimates near the contour. When the classical stereo correlation technique is applied and the search is made in the left image, the contour usually “leaks” to the right of the object boundary as illustrated in FIG. 2. Another set of errors are shown in the top left corner of FIG. 2 and are associated with out-of-focus objects that cannot be matched correctly. The present invention resolves each of these problems.
The prior art solutions used to successfully detect occlusions and avoid false correspondence require three or more cameras. In the simplest case, several cameras may be used to capture an image of the scene from equal angles along a hemisphere that surrounds the scene. Thus, if a point is not included in the second image, the first image may be matched to the third image and used to “complete” the occluded area in the second image. If not positioned properly, however, multiple camera stereos can increase the area of occlusion and may still lead to false correspondence. More specifically, depth maps generated from a polynocular stereo image often have blurred object shapes caused by the false correspondence at occluding boundaries.
Another set of solutions involved creative manipulation of a matching algorithm. Some matching algorithms may be better at avoiding false correspondence problems, but none solves the problem completely. For example, feature-based matching algorithms, which try to correspond points only at object edges, may be used to avoid occlusion to an extent. Other binocular stereo algorithms have also been adapted to try to detect “half-occluded” regions in order to improve the correspondence search. In both cases, however, the algorithms fail to measure the depth in these regions. More recently, new algorithms were developed for multiple camera devices, which may provide better results in occlusion detection.
In each prior art solution, either multiple cameras are needed to prevent occluded regions or the method is extremely time intensive and, in both cases, the resulting correspondence errors prevent creation of a complete depth map of the scene. Using multiple cameras increases the cost, burden and complexity of the imaging system, and the resulting images are still not amenable to depth analysis. What is needed, then, is a new method for detecting and eliminating occlusions and out-of-focus errors thereby enabling the creation of an accurate depth map of the scene without requiring significant time and effort to accomplish.